#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
using namespace std;

vector<int> findAnagrams(string s, string p) {
    vector<int> ans;
    int hash1[26] = { 0 };
    int hash2[26] = { 0 };
    for (auto e : p) ++hash2[e - 'a'];
    int m = p.size();
    int cnt = 0;
    for (int left = 0, right = 0; right < s.size(); ++right)
    {
        ++hash1[s[right] - 'a'];
        if (hash1[s[right] - 'a'] <= hash2[s[right] - 'a']) ++cnt;
        if (right - left + 1 > m)
        {
            if (hash1[s[left] - 'a']-- <= hash2[s[left] - 'a']) --cnt;
            ++left;
        }
        if (cnt == m)
            ans.push_back(left);
    }
    return ans;
}

int search(vector<int>& nums, int target) {
    int n = nums.size();
    if (!n)
        return -1;
    if (n == 1)
        return nums[0] == target ? 0 : -1;
    int left = 0, right = n - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
            return mid;
        if (nums[0] <= nums[mid])
        {
            if (nums[0] <= target && target < nums[mid])
                right = mid - 1;
            else
                left = mid + 1;
        }
        else
        {
            if (nums[mid] < target && target <= nums[n - 1])
                left = mid + 1;
            else
                right = mid - 1;
        }
    }
    return -1;
}


struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
    
};

int getDecimalValue(ListNode* head) {
    ListNode* cur = head;
    int ans = 0;
    for (; cur != nullptr; cur = cur->next)
    {
        ans = ans * 2 + cur->val;
    }
    return ans;
}
